module Árbol23 where

data Árbol23 a b = Hoja a | Dos b (Árbol23 a b) (Árbol23 a b) | Tres b b (Árbol23 a b) (Árbol23 a b) (Árbol23 a b)

{- Funciones para mostrar el Árbol. -}

instance (Show a, Show b) => Show (Árbol23 a b) where
    show x = concatMap (++"\n") (padTree 0 x)

padTree:: (Show a, Show b) => Int -> (Árbol23 a b)-> [String]
padTree i (Hoja x) = [(pad i) ++  (show x)]
padTree i (Dos x a1 a2) = [(pad i) ++  (show x) ] ++ (concatMap (padTree (i + 4)) [a1,a2])
padTree i (Tres x y a1 a2 a3) = [(pad i) ++  (show x) ++ (' ':(show y))] ++ (concatMap (padTree (i + 4)) [a1,a2,a3])

pad:: Int -> String
pad i = replicate i ' '

{- Funciones pedidas. -}

--foldA23:: funcH -> funcD -> funcT -> Árbol23 a b -> z
--foldA23:: ( a -> z ) -> funcD -> funcT -> Árbol23 a b -> z
--foldA23:: ( a -> z ) -> ( b -> z -> z -> z ) -> funcT -> Árbol23 a b -> z
foldA23 :: ( a -> z ) -> ( b -> z -> z -> z ) -> ( b -> b -> z -> z -> z -> z )  -> Árbol23 a b -> z
foldA23 casoHoja casoDos casoTres arbol = case arbol of
	Hoja d -> casoHoja d
	Dos k tl tr -> casoDos k (rec tl) (rec tr)
	Tres klm krm tl tm tr -> casoTres klm krm (rec tl) (rec tm) (rec tr)
	where rec = foldA23 casoHoja casoDos casoTres

--Lista en preorden de los internos del Árbol.
internos::Árbol23 a b->[b]
internos = foldA23
	(const [])
	(\key left right -> [key] ++ left ++ right)
	(\key1 key2 left middle right -> [key1] ++ [key2] ++ left ++ middle ++ right)

--Lista las hojas de izquierda a derecha.
hojas::Árbol23 a b->[a]
hojas = foldA23 
	(\x -> [x]) 
	(\_ left right -> left ++ right)
	(\_ _ left middle right -> left ++ middle ++ right)

--Determina si el árbol es una hoja
esHoja::Árbol23 a b->Bool
esHoja arbol = case arbol of
	Hoja _ -> True
	_ -> False

mapA23::(a->c)->(b->d)->Árbol23 a b->Árbol23 c d
--mapA23 funcValue funcKey arbol = foldA23 casoHoja casoDos casoTres arbol
--mapA23 funcValue funcKey = foldA23 casoHoja casoDos casoTres
mapA23 funcValue funcKey = foldA23
	(\x -> Hoja (funcValue x))
	(\key left right -> Dos (funcKey key) left right)
	(\key1 key2 left middle right -> Tres (funcKey key1) (funcKey key2) left middle right)

--Ejemplo de uso de mapA23.
--Incrementa en 1 el valor de las hojas.
incrementarHojas::Num a =>Árbol23 a b->Árbol23 a b
incrementarHojas = mapA23 (+1) id


--Trunca el Árbol hasta un determinado nivel. Cuando llega a 0, reemplaza el resto del Árbol por una hoja con el valor indicado.
--Funciona para Árboles infinitos.
truncar::a->Integer->Árbol23 a b->Árbol23 a b
truncar dato niveles arbol = trunc arbol niveles dato

trunc::Árbol23 a b->Integer->a->Árbol23 a b
trunc = foldA23
		(\d niveles dato -> ifniv niveles dato 
			(Hoja d) )
		(\key left right niveles dato -> ifniv niveles dato 
			(Dos key (rec left niveles dato) (rec right niveles dato) ) )
		(\key0 key1 left middle right niveles dato -> ifniv niveles dato 
			(Tres key0 key1 (rec left niveles dato) (rec middle niveles dato) (rec right niveles dato) ) )
		where
		rec a n d = a (n-1) d
		ifniv nivel dato func = if nivel > 0 then func else Hoja dato	

--Evalúa las funciones tomando los valores de los hijos como argumentos.
--En el caso de que haya 3 hijos, asocia a izquierda.
evaluar::Árbol23 a (a->a->a)->a
evaluar = foldA23 
	id
	(\f left right -> f left right)
	(\f1 f2 left middle right -> f2 (f1 left middle) right)

{- Árboles de ejemplo. -}
arbolito1::Árbol23 Char Int
arbolito1 = Tres 0 1
	      (Dos 2 (Hoja 'a') (Hoja 'b'))
	      (Tres 3 4 (Hoja 'c') (Hoja 'd') (Dos 5 (Hoja 'e') (Hoja 'f')))
	      (Dos 6 (Hoja 'g') (Dos 7 (Hoja 'h') (Hoja 'i')))

arbolito2::Árbol23 Int Bool
arbolito2 = Dos True (Hoja (-1)) (Tres False True (Hoja 0) (Hoja (-2)) (Hoja 4))

arbolito3::Árbol23 Int (Int->Int->Int)
arbolito3 = Dos (+) (Tres (*) (-) (Hoja 1) (Hoja 2) (Hoja 3)) (incrementarHojas arbolito3)

--Ejemplos:
--internos arbolito1 = [0,1,2,3,4,5,6,7]
--hojas arbolito1 = "abcdefghi"
--hojas (incrementarHojas arbolito2) = [0,1,-1,5]
--internos arbolito2 = [True,False,True]
--take 10 (hojas arbolito3) = [1,2,3,2,3,4,3,4,5,4]
--hojas (truncar 0 6 arbolito3) = [1,2,3,2,3,4,3,4,5,4,5,6,0,0,0,0,0]
--evaluar (truncar 0 6 arbolito3) = 22 = (1*2-3)+(2*3-4)+(3*4-5)+(4*5-6)
